ListNode链表结构超详细解析，LeetCode题解

2023-10-08 22:27| 来源: 网络整理| 查看: 265

LeetCode第二题两数之和中，用到了ListNode这么一个结构。记录下解题思路和步骤。

ListNode结构：

ListNode是一个链表结构，首先我们要知道链表是什么。

链表是由数据+指针构造而成的，指针指向下一个节点的数据。如下图：

所以我们在定义ListNode结构的时候，就需要定义两个属性，一个是当前节点的值，一个是下一个节点的ListNode类型的值，用来实现指针的功能。

class ListNode{ int val; //数据 ListNode next; //指向下一个节点的数据 }

可以加上构造函数：

class ListNode{ int val; ListNode next; ListNode(int x) { val = x; } ListNode(int x, ListNode y) { val = x; next = y; } }

假如说要定义[2, 4, 6]这么一个链表，也可以这么赋值，这样我感觉会更清晰的理解到链表的结构。

ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(6)));

题解：

清楚链表的结构后，回到题目上。原题如下：

题目的意思是，两个链表的数字都是按照逆序方式存储。

2->4->3，对应的数字是342；5->6->4，对应的数字是465。相加得出807，对应的链表是7->0->8。

所以，如果两个链表直接相加，得出来的数其实是不对的。这里存在一个满十进位的问题。正确的操作应该是，链表相同位置的值相加后再加上前一节点进位的数， % 10得出本节点的数，➗ 10得出进位数。如果加到最后一个节点，发现进位数>0，那么需要在链表的尾部追加进位数。

如果两个链表长度不一致，那么缺少的数可以视为0。

举个🌰：

以题中两个链表为例，第一位2 + 5 + 上一节点进位数 = 7，7 / 10 = 0 进位数为0；7 % 10 = 7, 头部节点为7。

第二位4 + 6 + 上一节点的进位数 = 10，10 / 10 = 1，进位数为1；10 % 10 = 0 ，本节点数为 0。

第三位3 + 4 + 上一节点的进位数1 = 7，7 / 10 = 0，进位数为0；7 % 10 = 7 ，本节点数为8。

结果值为7->0->8

再举个🌰：

[9,9,9]和[9,9]两个链表相加

第一位9 + 9 +上一节点的进位数= 18，18 / 10 = 1，进位数= 1；18 % 10 = 8 本节点数= 8；

第二位9 + 9 + 上一节点进位数1 = 19， 19 / 10 = 1，进位数=1；19 % 10 = 9 本节点数= 9；

第三位9 + 0 + 上一节点进位数1 = 10，10 / 10 = 1，进位数=1；10 % 10 = 0 本节点数 = 0；

注意这个地方最后一个节点计算完毕，进位数>0 ，所以需要再追加一位。结果值应该是8->9->0->1。

步骤：

下面就可以解题了，先捋一下解题的步骤：

首先要定义两个链表，一个是链表的结果值，也就是头部信息。一个是在循环相加链表时动态赋值的链表。如果不把链表的头部信息单独存放一份，在循环赋值中就会丢失前面的头部信息，只会保存最后一个值。循环遍历需要相加的两个链表，获取对应的值计算出本节点的数，和进位数，给我们定义的链表赋值。这里要注意，第一次循环时，需要判断链表头部是否为空，如果为空的话，就给头部赋值。循环结束后，判断进位数是否为1，是否需要尾部追加。

附上代码：

每一步都有注释解析。

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode curr = null; //循环中动态赋值的链表 ListNode head = null; //头部信息，也可以理解为最终的结果值 int s = 0; //初始的进位数 //循环遍历两个链表 while(l1 != null || l2 != null){ //取值 int num1 = l1 != null ? l1.val : 0; int num2 = l2 != null ? l2.val : 0; //两个值相加,加上上一次计算的进位数 int sum = num1 + num2 + s; //本次计算的进位数 s = sum / 10; //本次计算的个位数 int result = sum % 10; //给链表赋值 //判断链表头部是否为空 if(curr == null){ //先给curr链表赋值 curr = new ListNode(result); //指定head = curr，后续curr指向next节点重置节点信息时，head不会被重置 head = curr; }else{ //头部不为空，指定next节点信息 curr.next = new ListNode(result); //curr链表向后移，为了下一次循环继续给next节点赋值 curr = curr.next; } //同理，l1和l2链表向后移，获取下一节点信息 if(l1 != null){ l1 = l1.next; } if(l2 != null){ l2 = l2.next; } } //循环结束后判断进位数 if(s > 0) curr.next = new ListNode(s); //这里需要注意，是返回head链表，而不是curr。 //curr因为上面每次循环时，做了指针后移操作curr = curr.next; //如果返回curr，是最后一次循环的值，而不是全部链表。 return head; } }

结束。

【本文地址】

公司简介

联系我们